3695. LOGPOWER - n-th Power

Given an integer a, n and m, calculate r = aⁿ modulo m, ie. the remainder after dividing n-th power of a by the modulus m.

Input. The first line contains the numer of test cases t (t < 1000). Each of the next t lines contains 3 integers: a_i, n_i and m_i (-2³⁰ < a_i < 2³⁰, 0 < n_i < 2⁶⁰, 2 < m_i < 2³⁰).

Output. For each of test cases, output the number r_i – one in each line.

Sample input	Sample output
6 1 2 3 4 5 6 7 8 9 12 34 56 78 90 123 4567890 123456789012 34567890	1 4 4 16 42 781950

РЕШЕНИЕ

возвеение в степень

Анализ алгоритма

В задаче следует реализовать возведение в степень aⁿ mod m с оценкой сложности O(log₂n).

Реализация алгоритма

#include <stdio.h>

int tests;

long long a, n, m, res;

long long pow(long long a, long long n, long long m)

{

if (!n) return 1;

if (n & 1) return (a * pow((a * a) % m, n / 2, m)) % m;

return pow((a * a) % m, n / 2, m);

}

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%lld %lld %lld",&a,&n,&m);

res = pow(a,n,m);

printf("%lld\n",res);

}

return 0;

}